package MostElements.javaCode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;

public class MostElements {

    /**
     * 1.排序解法
     *
     * @param nums
     * @return
     */
    public static int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }

    /**
     * 2.map解法
     *
     * @param nums
     * @return
     */
    public static int majorityElement2(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
        Integer max = null;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() > nums.length / 2) {
                max = entry.getKey();
            }
        }
        return max;
    }

    /**
     * 分治算法
     *
     * @param nums
     * @return
     */
    public static int majorityElement3(int[] nums) {
        return partition(nums, 0, nums.length - 1);
    }

    /**
     * 分治算法
     * 递归算法
     * 把数组分成两个,如果是多数的话，那么分成的两个数组中一定有一个数是多数
     *
     * @param nums
     * @param min
     * @param max
     * @return
     */
    public static int partition(int[] nums, int min, int max) {
        if (min == max) {
            return nums[min];
        }

        //中位数
        int middle = (max - min) / 2 + min;
        // 左数组多数
        int left = partition(nums, min, middle);
        // 右数组多数
        int right = partition(nums, middle + 1, max);

        // 如果左右多数相同 ---> 那多数就是这个数
        if (left == right) {
            return left;
        }

        // 如果左右多数不相同 ---> 需要比较左右多数的数量，更多的即为整个数组的多数
        int leftCount = countInRange(nums, left, min, max);
        int rightCount = countInRange(nums, right, min, max);
        return leftCount > rightCount ? left : right;
    }

    /**
     * 计算num在nums中的个数
     *
     * @param nums
     * @param num
     * @param lo
     * @param hi
     * @return
     */
    private static int countInRange(int[] nums, int num, int lo, int hi) {
        int count = 0;
        for (int i = lo; i <= hi; i++) {
            if (nums[i] == num) {
                count++;
            }
        }
        return count;
    }

    /**
     * 投票算法
     * @param nums
     * @return
     */
    public static int majorityElement4(int[] nums) {
        int count = 0;
        Integer candidate = null;
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += num == candidate ? 1 : -1;
        }
        return candidate;
    }


    /**
     * 获取随机数
     * @param rand
     * @param min
     * @param max
     * @return
     */
    private static int randRange(Random rand, int min, int max) {
        return rand.nextInt(max - min) + min;
    }

    /**
     * 统计元素
     * @param nums
     * @param num
     * @return
     */
    private static int countOccurences(int[] nums, int num) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == num) {
                count++;
            }
        }
        return count;
    }

    /**
     * 随机算法
     * @param nums
     * @return
     */
    public static int majorityElement5(int[] nums) {
        Random rand = new Random();

        int majorityCount = nums.length / 2;

        while (true) {
            int candidate = nums[randRange(rand, 0, nums.length)];
            if (countOccurences(nums, candidate) > majorityCount) {
                return candidate;
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {1,1,1,3,4,5};
        int i = majorityElement5(nums);
        System.out.println(i);
    }
}
